TDD/TDMA Wireless technologies such as Bluetooth technology [BLU] allow for the replacement of the numerous proprietary cables that connect one device to another with a universal short-range radio link. Beyond untethering devices by replacing cables, such technologies provide a universal bridge to existing data networks, a peripheral interface, and a mechanism to form small private ad-hoc groupings of connected devices away from fixed network infrastructures. For example, interconnected devices in a Bluetooth system form a piconet, which can have one master and upto seven slaves.
The Bluetooth system is used as an example to explain the various aspects of this invention. Bluetooth has a number of distinctive features such as:                Support for both data and voice traffic        Frequency hopping to avoid interference        A Master driven Time Division Duplex (TDD) system at the Medium Access Control (MAC) layer to support full duplex transmission        Segmentation and Reassembly (SAR) to handle large data packets        
There are three basic protocols in any Bluetooth system: the Baseband Protocol, Link Manager Protocol (LMP) and Logical Link Control and Adaptation Protocol (L2CAP). The Baseband Protocol controls the hardware that turns the radio signals (transmit/receive) into a digital form that can be processed by the host application. LMP and L2CAP are layered above the Baseband Protocol and they reside in the datalink layer. LMP carries out link setup and authentication. L2CAP supports higher level protocol multiplexing, packet Segmentation and Reassembly (SAR), and also conveys quality of service information.
Segmentation and reassembly (SAR) operations are used to improve efficiency by supporting a maximum transmission unit (MTU) size larger than the largest baseband packet. This reduces overhead by spreading the network and transport packets used by higher layer protocols over several baseband packets.
SAR is performed at the L2CAP layer in which the L2CAP packets are divided into multiple baseband packets covering 1, 3 or 5 slots. These baseband packets are then enqueued into the baseband buffer. Using a Medium Access Control (MAC) scheduling algorithm, these packets are sent at appropriate intervals over the RF link.
In the future, Bluetooth will seek to support communication-intensive applications such as multimedia teleconferencing, WWW browsing, etc. Supporting such applications requires the network to maintain sustained quality of service (QoS) to packet flows over scarce wireless resources. In wireline networks, QoS requirements are typically satisfied by a combination of resource reservation (at the flow level) and fair resource allocation/packet scheduling (at the packet level).
However, the problem of fair packet scheduling in Bluetooth has remained largely unaddressed.
In Bluetooth systems, conventional scheduling policies such as Round Robin perform poorly as they are not suited for tight coupling of uplink-downlink scheduling and result in slot wastage and unfairness. Scheduling in Bluetooth is complex due to variable sized data packets. Bluetooth uses a Master-driven time division duplexed (TDD) slot structure for resolving contention over the wireless links. There is a strict alternation of slots between the Master and the Slaves. The Master can only send packets to a Slave in even slots while the slave can send packets to the Master in an odd slot [BLU]. Further, the task of scheduling is vested with the Master. Note that from the above description, it is not difficult to infer that there could be a wastage of slots in the TDD scheme, since if only one of the Master or the Slave has data to send, a slot gets wasted.
Another important issue in MAC (Medium Access Control) scheduling is that of fairness. A desirable scheduler is one that minimizes maximum session completion times, fairly distributes bandwidth among all active sessions and minimizes delay for interactive sessions. Efficient MAC scheduling algorithms need to be designed for Bluetooth systems to maximize slot utilzation and hence improve the channel throughput.
A number of approaches for scheduling in wireless networks have been studied earlier. In [KAL] two new scheduling algorithms are identified for Bluetooth. These policies use information about the size of the HOL (head of the line) packet to schedule TDD slots effectively. The new policies are HOL Priority and HOL K-fairness. Channel state dependent packet scheduling (CSDP) policies to improve TCP throughout over wireless LANs have been proposed in [BHA].
U.S. patent application Ser. No. 09/434,583 (issued as U.S. Pat. No. 6,680,909) describes a scheduling method that gives high system throughput and fairness amongst different connections in a wireless network.
In U.S. Pat. No. 6,075,791, a system is disclosed which services a plurality of queues associated with respective data connections such that the system guarantees data transfer rates and data transfer delays to the data connections. This is achieved by associating each connection having at least one data packet waiting in its associated queue with a timestamp generated as a function of system parameters such as the number of queues that are backlogged, (b) the data transfer rate guaranteed to each connection, each timestamp weighted by the data transfer rate guaranteed to the corresponding connection. This system, however, is not optimized for wireless networks such as Bluetooth.
In U.S. Pat. No. 4,949,395, a method is described for dynamically allocating time slots to connections on the radio channels, in order to increase the capacity on the radio channels. The maximum number of simultaneous connections on the radio channels is more than the available number of the time slots per frame. When there are more connections established on a first and a second radio channel than time slots per frame, the connections share the available time slots in accordance with a determined multiframe time slot allocation scheme known to the base station and the mobile stations. However, this method cannot be directly applied to Bluetooth as it has characteristics distinct from the mobile network scenario discussed in this method.
In U.S. Pat. No. 6,069,885, a method for scheduling transmissions between a plurality of communication sites within a wireless system. The system provides service to an area divided into sectors, each of which communicate information in at least one time subframe according to a schedule that minimizes interference between sites.
In U.S. Pat. No. 5,844,890, a method and apparatus are provided for scheduling the transmission of cells of a plurality of data streams in a communications network. A best effort scheduler is provided for scheduling the transmission of cells of a plurality of data streams in a communications network. This work is, however, not optimized for a wireless network.
In the case of Bluetooth, Segmentation and Reassembly (SAR) schemes have not been studied earlier in detail. In [KAL], two new Segmentation and Reassembly (SAR) policies, ISAR and Adaptive SAR, are identified for Bluetooth, keeping data flow in mind, but an exact algorithm for this purpose is not described. These algorithms consider only the packet size distribution at the baseband level, but do not account for the effect of Segmentation and Reassembly (SAR) on application data packets of varying sizes.
In International Patent application No. WO09904521A2, a method and apparatus for providing segmentation and reassembly over wireless and satellite links is provided. Variable sized packets are divided into segments having a size equal to that of an Asynchronous transfer mode (ATM) cell and are then arranged in a Segmentation and Reassembly (SAR) frame having in its overhead an indication as to the length and unique identity of the frame, each segment also having a header that uniquely identifies the segment. This method applies only to an ATM scenario and cannot be directly applied to Bluetooth.
A method for partitioning data load and unload functions within an interface system for use with an ATM system is discussed in U.S. Pat. No. 5,625,625. For segmentation, a transmit load engine controls storage of data from packets into an external buffer memory; whereas receive unload engine handles extraction of data from memory, segmenting data into cells and transmitting cells to the ATM system. For reassembly, a receive load engine handles receiving and storing the cells corresponding to the packets into a memory; whereas a receive unload engine controls extraction of data from memory and transmission to the system. The Segmentation and Reassembly (SAR) controller is designed for an ATM system and must be significantly changed for use in Bluetooth.